// https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/

// 算法思路总结：
// 1. 二分查找寻找山脉数组的峰值索引
// 2. 根据中点与相邻元素关系判断峰值位置
// 3. 中点处于上升区间时向右收缩查找范围
// 4. 中点处于下降区间时向左收缩查找范围
// 5. 时间复杂度：O(log n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int m = arr.size();
        int l = 0, r = m - 1;

        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (arr[mid] < arr[mid + 1] && arr[mid] > arr[mid - 1])
            {
                l = mid;
            }
            else if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
            {
                r = mid;
            }
            else
            {
                l = mid;
            }
        }
        
        return l;
    }
};

int main()
{
    vector<int> arr1 = {0,1,0}, arr2 = {0,10,5,2};
    Solution sol;

    cout << sol.peakIndexInMountainArray(arr1) << endl;
    cout << sol.peakIndexInMountainArray(arr2) << endl;

    return 0;
}